The present invention relates generally to communication networks, and specifically to transmission of audio data in ATM networks.
Asynchronous Transfer Mode (ATM) has been widely accepted as a packet switching communications standard for high-speed, Broadband Integrated Services Digital Networks (B-ISDN). ATM networks are designed to carry a mixture of data, voice and video on common circuits. An ATM packet, or cell, comprises 53 bytes, including a five-byte header and 48-byte payload.
The International Telecommunications Union (ITU) has promulgated standard I.363.2, xe2x80x9cB-ISDN ATM Adaptation Layer Type 2 Specificationxe2x80x9d (September, 1997), known as AAL-2, in order to enable efficient transmission of real-time voice-band data over ATM networks. The standard, which is incorporated herein by reference, defines how traffic in the form of packets of various numbers of octets (or bytes) are assembled into ATM cell payloads at a transmitter and disassembled back into the original packet stream at the receiver.
ITU standard I.366.2, xe2x80x9cAAL Type 2 Service Specific Convergence Sublaver for Trunking,xe2x80x9d which is incorporated herein by reference, defines several types of packet formats for voice-band data, which are encoded into packets of variable length. A Type-1 packet, as defined by this standard, has no explicit identifier for the encoding algorithm used. The encoding algorithm is implicitly identified, however, by a combination of the packet length, a parameter in the packet header (a user-user interface code, or UUI), and a predefined profile agreed upon between the transmitter and the receiver. The standard identifies the profile as xe2x80x9ca mapping that informs the receiver of a Type-1 audio packet how to interpret the packet content. The domain of this mapping is a set of pairs (UUI, Length).xe2x80x9d The first element of each pair is a UUI codepoint in the range 0-15, which is utilized in part to indicate a packet sequence number. The second element is the packet length for one of the encoding formats included in the profile. Each Type-1 packet may include multiple encoded packets, or sub-packets.
Each encoding algorithm produces some minimum encoded packet length, dependent on the encoding bit rate. For example, packets encoded using the LD-CELP algorithm, in accordance with standard G.728 of the ITU, have minimum packet lengths of 10, 8 and 6 octets, respectively, for bit rates of 16, 12.8 and 9.6 Kbit/s, at which the LD-CELP algorithm is conventionally allowed to work. A profile may also include a combination of encoded packets with more than one minimum length interval, if no ambiguity occurs as a result. Thus, for example, the profile may include LD-CEL encoded packets of lengths 20, 16 and 12 octets. Part of the UUI field may be used to expand the profile if ambiguity does occur. The cost of expanding the number of bits allocated to the profile is that the modulus of the packet sequence number, which is used to detect irregularities in the packet stream at the receiving end, is reduced.
The alternative packet lengths and corresponding bit rates of a given encoding scheme may be used for controlling traffic rate at the input to an ATM network from a transmission source. This technique is known generally as variable rate encoding (VRE). The ITU defines VRE for use in voice transmission over ATM network as xe2x80x9cthe capability of the encoding algorithm to dynamically switch between the nominal bit rate to lower or higher discrete bit rates under the control of the ATM equipment.xe2x80x9d
How VRE is Performed depends on the signal type, for example, speech, fax or modem, and the kind of encoding algorithm used, such as the ADPCM, LD-CELP or CS-ACELP algorithms, for example, which are defined by the ITU G. 726, G.728 and G.729 standards, respectively. For each particular signal type and algorithm, there is a set of applicable, discrete output bit rates, such as the LD-CELP rates of 9.6, 12.8 and 15 Kbit/s mentioned above. A VBD-modem signal, as defined by the G.726 standard, is commonly encoded at 40 Kbit/s. Typically, VRE on speech signals is performed by selecting among the applicable bit rates. Another option, useful for fax signals with forward error correction (FEC), for example, is to change the bit rate by using or not using additional FEC bits.
The use of VRE is generally required in the following situations:
When the traffic load in a specific ATM Virtual Circuit (VC) is higher than the bandwidth allowed by contract with the network being used; or
When the sum of the traffic loads in all of the VC""s that share a common link exceeds the link bandwidth.
Both of these conditions may occur simultaneously. There is also the possibility that traffic load on a given Virtual Path (VP, as defined by the ITU and ATM Forum), which serves a number of VC""s, mav exceed a contractual bandwidth.
U.S. Pat. No. 5,646,943, to Elwalid, which is incorporated herein by reference, describes a congestion control method in which an access regulator limits the rate of input data to a network node. A rate parameter of the access regulator is dynamically adjusted according to a level of congestion in the node.
U.S. Pat. No. 5,805,577, to Jain, et al., which is incorporated herein by reference, similarly describes a congestion avoidance scheme for data traffic in ATM networks. Input data rates from a number of active sources transmitting data via a network switch are measured and used to determine an overload factor relative to available bit rate capacity. The overload factor is used to dynamically determine a fair share allocation of transmission capacity among the sources. The transmission rates of the sources are adjusted so as not to exceed the respectively allocated capacity. This scheme is complex and computationally heavy, since it requires that the input data rates be measured, and that all of the queues associated with the data sources be viewed and taken into account.
U.S. Pat. No. 5,463,620, to Sriram, and an article by Sriram entitled xe2x80x9cMethodologies for Bandwidth Allocation, Transmission Scheduling, and Congestion Avoidance in Broadband ATM Networks,xe2x80x9d in Computer Networks and ISDN Systems 26 (1993), pp. 43-59, which are incorporated herein by reference, describe a congestion control mechanism using bit-dropping of packetized voice data. When congestion occurs, traffic loads is reduced by dropping the least-significant bits of already-encoded voice packets.
It is an object of the present invention to provide an improved method for congestion control in ATM networks.
It is a further object of some aspects of the present invention to provide a method for congestion control that is particularly applicable to voice-band data utilizing the AAL-2 standard.
In preferred embodiments of the present invention, one or more variable-rate encoders generate encoded data for transmission via a virtual circuit (VC) over an ATM network. A degree of circuit congestion, or stress, is determined, based on a level of congestion of the network encountered by the VC. The stress level is fed back to the encoders, which vary their encoding rates responsive thereto, so as to adjust their output bit rate to the congestion level.
In some preferred embodiments of the present invention, the encoded data are assembled into cells, preferably using an AAL-2 service, as is known in the ATM art. The cells enter a cell queue for transmission via the VC. A fill level of the cell queue, i.e., an expected length of the queuing delay, is used to determine the stress level for controlling the encoding rates of the encoders.
In some preferred embodiments of the present invention, a plurality of VC""s, each with its own cell queue, are multiplexed over a network link. The stress level for each VC, as well as the corresponding encoding rates of the one or more encoders associated with the VC, is determined substantially independently for each of rune VC""s. Mutual influence among the VC stress levels is felt indirectly, however, when network bandwidth limitations cause some or all of the VC cell queues to lengthen as a result of the aggregate input traffic level of all the VC""s.
In some preferred embodiments of the present invention, the output bit rate of the one or more encoders is reduced below a nominal, maximal value even when the stress level is low. Preferably, the reduction is implemented statistically, i.e., a reduced encoding rate is used intermittently, at statistically-determined intervals. The reduced bit rate enables a constant, although mildly reduced, voice transmission quality level to be maintained, generally independent of network load. It also reduces the VC bandwidth requirement, enabling a user of the VC to save on network contract costs and/or to use available bandwidth for transmission of additional data, typically non-real time data, such as electronic mail. Further preferably, statistical control of the encoding rate is maintained under both congested and non-congested network conditions, so that the transition from one condition to the other is smooth, without an abrupt change in transmission quality.
In some preferred embodiments of the present invention, an ambiguity-resolving field (ARF), preferably one octet in length, is attached to the head or tail of a packet for transmission. Using the ARF, an AAL-2 Type-1 profile is expanded so as to identify the lengths of sub-packets contained in the packet, which would otherwise be ambiguous. Preferably, a part of the ARF is used for error detection and correction of the ARF itself, using a CRC-3 code, for example. The ARF allows the limited range of Type-1 profiles to be substantially expanded, so that a greater variety of sub-packet sizes can be used in a single packet. As a result, successive sub-packets output by an encoder and grouped in a single Type-1 packet can have different lengths, unlike Type-1 packets known in the art. The encoding rate can thus be varied at a higher frequency than would be possible if only ordinary Type-1 profiles were used.
There is therefore provided, in accordance with a preferred embodiment of the present invention, variable-rate encoding apparatus operative to receive data and process the data for transmission through an asynchronous transfer mode network, including:
a processor, which determines a degree of circuit congestion associated with at least one virtual circuit of the network; and
a variable-rate encoder, operative to encode the received data so as to provide encoded data packets to the at least one virtual circuit at a rate that is selected responsive to the degree of circuit congestion.
Preferably, the degree of the circuit congestion is determined responsive to the status of a cell queue associated with the at least one virtual circuit, wherein the degree of the circuit congestion is proportional to a ratio of an instantaneous fill level of the cell queue to a maximum fill level of the cell queue.
Further preferably, the processor determines a mean bit rate of the encoded data packets to be output by the encoder as a function of the circuit congestion, and including a bit rate selector, which selects one of a plurality of discrete, applicable bit rates of the encoder responsive to the mean bit rate. Most preferably, each of the applicable bit rates is respectively associated with an output data packet length determined by an encoding standard according to which the encoder encodes the data. Further preferably, the mean bit rate determined for a minimum value of the circuit congestion is less than a maximum of the applicable bit rates. In a preferred embodiment, for a given mean bit rate, the bit rate selector alternately selects at least two different ones of the applicable bit rates, wherein the selection among the at least two different applicable bit rates is randomized.
Preferably, the rate at which the encoder encodes the data is selected responsive to an optimal average number of output bits per data sample, which is determined independently of the circuit congestion. Most preferably, the processor determines a desired bit rate of the encoded data packets to be output by the encoder by comparing a mean bit rate determined as a function of the circuit congestion and an optimal bit rate determined as a function of the optimal average number of output bits per data sample.
In a preferred embodiment, the apparatus generates ATM Adaptation Layer 2 Type-1 packets for transmission through the network, including a Type-1 packet in which two or more of the encoded data packets, differing in at least one defining characteristic, are combined. Preferably, an ambiguity-resolving field is appended to at least one of the Type-1 packets so as to identify the characteristics of the encoded data packets combined therein.
There is further provided, in accordance with a preferred embodiment of the present invention, a variable-rate encoding system for processing data received from multiple data sources for transmission through an asynchronous transfer mode network, including:
one or more cell queues, which contain cells prepared for transmission through respective virtual circuits or virtual paths of the network and have respective queue fill levels; and
one or more variable-rate encoders, each of which provides encoded data packets to one of the cell queues after encoding the data at a rate that is varied responsive to the fill level of the cell queue to which the packets are provided.
Preferably, the one or more cell queues include a plurality of cell queues, whose respective fill levels vary responsive to a level of network congestion. Most preferably, the encoding rate for each of the encoders is set responsive to the level of the one of the plurality of cell queues to which the encoder provides the encoded data packets, substantially independently of setting the encoding rate of the other encoders.
There is additionally provided, in accordance with a preferred embodiment of the present invention, variable-rate encoding apparatus for processing data received for transmission through an asynchronous transfer mode network, including a variable-rate encoder, which encodes the received data so as to provide encoded data sub-packets having different encoding characteristics, the encoder being operative to combine two or more of the sub-packets into a Type-1 packet, and to attach an ambiguity-resolving field to the Type-1 packet when required so as to identify the encoding characteristics of the sub-packets contained in the packet.
Preferably, the different encoding characteristics include respective lengths of the sub-packets, wherein the Type-1 packet includes two or more sub-packets of different lengths. Further preferably, the different lengths are associated with respective, different encoding rates, which are selected from a plurality of discrete, applicable bit rates of the encoder.
In a preferred embodiment, the different encoding characteristics include different encoding rules that are applied by the encoder.
There is moreover provided, in accordance with a preferred embodiment of the present invention, a method for variable-rate encoding of data from a data source for transmission through a virtual circuit in an asynchronous transfer mode network, including:
encoding data from the source so as to provide encoded data packets to the virtual circuit at a variable output bit rate;
determining a degree of circuit congestion associated with the virtual circuit; and
controlling the encoding so as to set the output bit rate responsive to the degree of circuit congestion.
Preferably, determining the degree of circuit congestion includes assessing the status of a cell queue associated with the virtual circuit, wherein assessing the status of the cell queue includes evaluating a ratio of a fill level of the cell queue to a maximum fill level of the cell queue.
Further preferably, controlling the encoding includes determining a mean bit rate of the encoded data packets to be output as a function of the circuit congestion, and selecting one of a plurality of discrete, applicable bit rates responsive to the mean bit rate. Most preferably, selecting the one of the applicable bit rates includes selecting an output data packet length associated with the respective bit rate, as determined by an applicable encoding standard. Further preferably, determining the mean bit rate includes setting a mean bit rate at a minimum value of the circuit congestion that is substantially less than a maximum of the applicable bit rates.
In a preferred embodiment, selecting the one of the applicable bit rates includes, for a given mean bit rate, alternately selecting at least two different ones of the applicable bit rates, wherein alternately selecting the at least two different applicable bit rates includes making a randomized selection.
Preferably, controlling the encoding includes selecting a rate at which the data are encoded responsive to an optimal average number of output bits per data sample, which is determined independently of the circuit congestion. Most preferably, selecting the rate at which the data are encoded includes selecting a rate based on comparing a measured mean bit rate and an optimal bit rate determined as a function of the optimal average number of output bits per data sample.
In a preferred embodiment, the method includes combining two or more encoded data packets differing in at least one defining characteristic thereof into a single ATM Adaptation Layer 2 Type-1 packet for input to the virtual circuit. Preferably, combining the two or more encoded data packets includes appending an ambiguity-resolving field to the Type-1 packet so as to identify the characteristics of the encoded data packets combined therein.
Preferably, encoding the data includes encoding data from multiple sources for transmission through a plurality of virtual circuits in the network, each circuit characterized by a respective circuit congestion dependent on congestion of the network, and controlling the encoding includes varying an output bit rate of each of the sources substantially independently of the other sources. Most preferably, varying the output bit rate of each of the sources includes varying a bit rate responsive to a fill level of a cell queue associated with a respective one of the virtual circuits to which the encoded data from the source are provided.
There is further provided, in accordance with a preferred embodiment of the present invention, a method for variable-rate encoding of data from a data source for transmission through an asynchronous transfer mode network, including:
encoding data from the source so as to provide encoded data sub-packets having different encoding characteristics;
combining one or more of the sub-packets in an ATM Adaptation Layer 2 Type-1 packet; and
attaching an ambiguity-resolving field to the Type-1 packet so as to identify the encoding characteristics of the one or more sub-packets contained in the packet.
Preferably, encoding the data includes providing sub-packets having different, respective lengths, wherein combining the sub-packets includes combining sub-packets of different lengths.
Additionally or alternatively, encoding the data includes encoding data at different encoding rates, which are selected from a plurality of discrete, applicable bit rates of the encoder.
In a preferred embodiment, encoding the data includes applying different encoding rules to the sub-packets.
The present invention will be more fully understood from the following detailed description of the preferred embodiments thereof, taken together with the drawings in which: